/*
 * Copyright 北京航空航天大学  @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * <p>二叉树层序遍历</p>
 * @author towan
 * @email tongwenzide@163.com
 * @time 2015年6月14日
 */
public class BinaryTreeZigzagLevelOrderTraversal {

   public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
       List<List<Integer>> result = new ArrayList<>();
       if(root==null) return result;
       //记录当前层的所有节点
       LinkedList<TreeNode> curLevel = new LinkedList<>();
       curLevel.add(root);
       boolean leftToRight  = true;
       while(curLevel.size()>0){
           ArrayList<Integer> currList = new ArrayList<>();
           LinkedList<TreeNode> nextLevel = new LinkedList<>();
           while(curLevel.size()>0){
               //移除队列头的元素
               TreeNode node = curLevel.poll();
               //如果有左右节点加入下一层队列
               if(node.left!=null) nextLevel.add(node.left);
               if(node.right!=null) nextLevel.add(node.right);
               
               if(leftToRight){
                   currList.add(node.val);
               }else{
                   //将右边结点加到前面
                   currList.add(0, node.val);
               }
           }
           result.add(currList);
           curLevel = nextLevel;
           leftToRight = !leftToRight;//变化顺序
       }
      return result; 
    }
}
